/*
==================================================================
* 版权所有 © 2025 CaryXiong
* Copyright (C) 2025 CaryXiong(a1816101108@outlook.com)
*
* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/.
===================================================================
*/




#include<iostream>
using namespace std;

const int StackSize = 20;

template<class DataType>
class SeqStack{
    public:
        SeqStack();
        SeqStack(DataType a[], int n);
        ~SeqStack();
        void Push(DataType x);
        DataType Pop();
        DataType GetTop();
        bool Empty();

        void Print();
        void Sort1();
        void Sort2();

    private:
        DataType data[StackSize];
        int top;
};

template<class DataType>
SeqStack<DataType> :: SeqStack(){
    top = -1;
}

template<class DataType>
SeqStack<DataType> :: SeqStack(DataType a[], int n){
    if(n>StackSize) throw "长度不足";
    for(int i=0; i<n; i++){
        data[i] = a[i];
    }
    top = n-1;
}

template<class DataType>
SeqStack<DataType> :: ~SeqStack(){
    ;
}

template<class DataType>
void SeqStack<DataType> :: Push(DataType x){
    if(top == StackSize-1) throw "长度不足";
    data[top+1] = x;
    top++;
}

template<class DataType>
DataType SeqStack<DataType> :: Pop(){
    DataType value = data[top];
    top--;
    return value;
}

template<class DataType>
DataType SeqStack<DataType> :: GetTop(){
    return data[top];
}

template<class DataType>
bool SeqStack<DataType> :: Empty(){
    if(top == -1) return true;
    else return false;
}

template<class DataType>
void SeqStack<DataType> :: Print(){
    for(int i=0; i<=top; i++){
        cout << data[i] << "\t";
    }
    cout << endl;
}

template<class DataType>
void SeqStack<DataType> :: Sort1(){
    int length = top+1;
    DataType temp[top+1];
    for(int i=0; top!=-1; i++){
        temp[i] = Pop();
    }
    for(int i=0; i<length; i++){
        Push(temp[i]);
    }
}

template<class DataType>
void SeqStack<DataType> :: Sort2(){
    int length = top+1;
    DataType temp1[length/2], temp2[length/2], temp;

    for(int i=0; i<length; i++){
        temp = Pop();
        if(i%2 == 0) temp1[i/2]=temp;
        else temp2[i/2]=temp;
    }

    for(int i=length/2-1; i>=0; i--){
        Push(temp2[i]);
    }
    for(int i=length/2-1; i>=0; i--){
        Push(temp1[i]);
    }
}








template<class DataType>
class Share_SeqStack{
    public:
        Share_SeqStack();
        Share_SeqStack(DataType a1[], DataType a2[], int n1, int n2);
        void Push(DataType x, int statue);
        DataType Pop(int statue);
        DataType GetTop(int statue);
        bool Empty(int statue);

        void Print(int statue);
    private:
        DataType data[StackSize];
        int top1, top2;
};

template<class DataType>
Share_SeqStack<DataType> :: Share_SeqStack(){
    top1 = -1;
    top2 = StackSize;
}

template<class DataType>
Share_SeqStack<DataType> :: Share_SeqStack(DataType a1[], DataType a2[], int n1, int n2){
    if(n1+n2 > StackSize) throw "容量不足";
    for(int i=0; i<n1; i++){
        data[i] = a1[i];
    }
    for(int i=0; i<n2; i++){
        data[StackSize-1-i] = a2[i];
    }
    top1 = n1-1;
    top2 = StackSize-n2;
}

template<class DataType>
void Share_SeqStack<DataType> :: Push(DataType x, int staute){
    /*
    入栈操作 statue取值为1或2
    statue = 1  入第一个栈
    statue = 2  入第二个栈
    */
    if(top1 == top2) throw "容量不足，无法入栈";
    if(staute == 1){
        data[top1+1] = x;
        top1 ++;
    }
    if(staute == 2){
        data[top2-1] = x;
        top2 --;
    }
}

template<class DataType>
DataType Share_SeqStack<DataType> :: Pop(int statue){
    DataType value;
    if(statue == 1){
        value = data[top1];
        top1--;
        return value;
    }
    if(statue == 2){
        value = data[top2];
        top2++;
        return value;
    }
    return -1;
}

template<class DataType>
DataType Share_SeqStack<DataType> :: GetTop(int statue){
    if(statue == 1){
        return data[top1];
    }
    if(statue == 2){
        return data[top2];
    }
    return -1;
}

template<class DataType>
bool Share_SeqStack<DataType> :: Empty(int statue){
    if(statue == 1){
        if(top1 == -1) return true;
        else return false;
    }
    if(statue == 2){
        if(top2 == -1) return true;
        else return false;
    }
}

template<class DataType>
void Share_SeqStack<DataType> :: Print(int statue){
    if(statue == 1){
        for(int i=0; i<=top1; i++){
            cout << data[i] << '\t';
        }
        cout << endl;
    }else{
        for(int i=StackSize-1; i>=top2; i--){
            cout << data[i] << '\t';
        }
        cout << endl;
    }
}









int main(){
    cout << "测试SeqStack：" << endl;
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    SeqStack<int> S1(a,10);

    cout << "当前顺序栈内容：";
    S1.Print();

    cout << "向顺序栈中Push元素100：" << endl;
    S1.Push(100);
    cout << "当前顺序栈内容：";
    S1.Print();

    cout << "弹出顺序栈的栈顶元素：" << S1.Pop() << endl;
    cout << "当前顺序栈内容：";
    S1.Print();

    cout << "获取当前栈顶元素：" << S1.GetTop() << endl;

    cout << "判断当前顺序栈是否为空：";
    if(S1.Empty()) cout << "空" << endl;
    else cout << "非空" << endl;

    cout << "调用Sort1，将该顺序栈逆置：";
    S1.Sort1();
    S1.Print();
    
    cout << "调用Sort2：";
    S1.Sort2();
    S1.Print();

    cout << endl << endl << endl;

    cout << "***********下面开始测试共享栈***********" << endl << endl;
    int b1[8] = {1,2,3,4,5,6,7,8}, b2[8] = {11,22,33,44,55,66,77,88};
    Share_SeqStack<int> S2(b1,b2,8,8);
    
    cout << "当前顺序栈1内容：";
    S2.Print(1);
    cout << "当前顺序栈2内容：";
    S2.Print(2);

    cout << "获取栈1的栈顶元素：" << S2.GetTop(1) << endl;
    cout << "获取栈2的栈顶元素：" << S2.GetTop(2) << endl;

    cout << "弹出栈1的栈顶元素：" << S2.Pop(1) << endl;
    cout << "当前顺序栈1内容：";
    S2.Print(1);
    cout << "弹出栈2的栈顶元素：" << S2.Pop(2) << endl;
    cout << "当前顺序栈2内容：";
    S2.Print(2);

    cout << "将元素100 Push到栈1中：";
    S2.Push(100,1);
    S2.Print(1);

    cout << "将元素200 Push到栈1中：";
    S2.Push(200,2);
    S2.Print(2);

    int c;
    cin >> c;
}